Hash Collision

contents

1. 핵심 개념: 해시 충돌이란 무엇인가?

해시 함수(Hash Function) 는 임의의 크기를 가진 입력값(문자열, 객체, 파일 등)을 받아서 고정된 크기의 정수("해시 코드")로 뒤섞습니다. 이 정수는 배열("해시 테이블")에 데이터를 저장하기 위한 인덱스(색인) 역할을 합니다.

충돌(Collision) 은 해시 함수가 서로 다른 두 개의 입력값을 받았는데 완벽히 똑같은 결과(인덱스) 를 뱉어낼 때 발생합니다.

왜 이런 일이 발생할까요? 비둘기집 원리(Pigeonhole Principle) 때문입니다.

비둘기집(배열의 버킷)이 10개인데 비둘기(데이터)가 11마리라고 상상해 보세요. 수학적으로 어떻게 배치하든 적어도 하나의 집에는 반드시 두 마리 이상의 비둘기가 들어가야 합니다.

입력 가능한 값의 우주(우리가 타이핑할 수 있는 모든 문자열)는 고정된 크기의 배열보다 무한히 크기 때문에, 충돌은 단순히 "일어날 수 있는 일"이 아니라 "무조건 일어나는 일(Guaranteed)" 입니다.

2. 충돌 해결 전략 A: 체이닝 (Separate Chaining / Open Hashing)

가장 널리 쓰이는 방식이며, Java의 HashMap이 정확히 이 방법을 사용합니다.

배열의 버킷에 실제 데이터를 직접 저장하는 대신, 배열은 데이터 구조(주로 연결 리스트, Linked List)를 가리키는 포인터를 저장합니다.

작동 방식:

1. 삽입: "Apple"을 해싱해서 인덱스 4가 나왔습니다. 인덱스 4의 연결 리스트에 "Apple"을 넣습니다.
2. 충돌: "Banana"를 해싱했는데 똑같이 인덱스 4가 나왔습니다.
3. 해결: 인덱스 4에 이미 존재하는 연결 리스트의 맨 끝에 "Banana"를 덧붙이기만 하면 됩니다.

"성능 저하(Degradation)" 문제와 현대적 해결책

• 문제점: 만약 1,000개의 데이터가 전부 인덱스 4에서 충돌한다면, 번개처럼 빠른 $O(1)$ 성능의 해시 테이블이 느려터진 $O(n)$의 연결 리스트로 전락해버립니다.
• 현대적 해결책 (Java 8 이상): 단일 버킷의 연결 리스트가 특정 임계치(Java의 경우 8개)에 도달하면, 테이블은 자동으로 해당 연결 리스트를 레드-블랙 트리(Red-Black Tree) 로 변환합니다. 이를 통해 최악의 충돌 시나리오에서도 검색 시간이 $O(n)$이 아닌 $O(\log n)$으로 우아하게 방어됩니다.

3. 충돌 해결 전략 B: 개방 주소법 (Open Addressing / Closed Hashing)

이 전략에서는 연결 리스트나 외부 데이터 구조를 전혀 사용하지 않습니다. 모든 데이터는 오직 배열 내부(Strictly inside the array)에만 저장됩니다. 해싱을 했는데 목표 버킷이 이미 꽉 차 있다면, 시스템은 바로 다음 번 빈 버킷을 찾아(Probing) 그곳에 데이터를 넣습니다.

탐사(Probing)에는 세 가지 주요 방식이 있습니다:

1. 선형 탐사 (Linear Probing)

버킷 i가 꽉 찼다면, i+1을 확인합니다. 거기도 찼다면 i+2를 확인하고, 배열 끝에 도달하면 필요시 다시 처음으로 돌아갑니다.

• 장점: 매우 빠르고 캐시 친화적(Cache-friendly)입니다 (CPU 캐시는 연속된 메모리를 좋아합니다).
• 단점: 1차 군집화 (Primary Clustering). 충돌이 발생하면 데이터들이 덩어리(블록) 형태로 연속해서 뭉치기 시작합니다. 새로운 데이터가 이 덩어리에 부딪히면 덩어리가 더 커지며 마치 교통 체증처럼 작동합니다.

2. 이차 탐사 (Quadratic Probing)

선형 탐사의 "교통 체증"을 막기 위해, 제곱수를 이용해 점프 간격을 벌립니다.

버킷 i가 찼다면, $i + 1^2$ (1칸 건너뜀)을 확인합니다. 거기도 찼다면 $i + 2^2$ (4칸 건너뜀)을 확인하고, 그다음은 $i + 3^2$ (9칸 건너뜀)을 확인합니다.

• 장점: 1차 군집화 문제를 해결합니다.
• 단점: 2차 군집화 (Secondary Clustering). 만약 서로 다른 두 키가 해싱을 통해 완벽히 동일한 초기 버킷에 배정된다면, 점프하는 궤적마저 똑같아져서 결국 새로운 형태의 군집을 형성하게 됩니다.

3. 이중 해싱 (Double Hashing - 최고의 개방 주소법)

첫 번째 해시 함수에서 충돌이 나면, 키를 완전히 다른 두 번째 해시 함수에 통과시켜서 점프할 보폭(크기)을 결정합니다.

• 장점: 1차 및 2차 군집화를 모두 완벽히 제거합니다. 점프 궤적이 매우 무작위적입니다.
• 단점: 해시 연산을 여러 번 해야 하므로 상대적으로 느립니다.

4. 충돌을 최소화하는 방법 (예방)

충돌을 완전히 없앨 수는 없지만, 두 가지 주요 방법을 통해 획기적으로 줄일 수 있습니다.

A. 균일한 해시 함수 (Uniform Hash Function)

나쁜 해시 함수는 데이터를 버킷 1, 2, 3에만 몰아넣습니다. 좋은 해시 함수(MurmurHash나 CityHash 등)는 데이터를 마치 무작위처럼 보이게끔 사용 가능한 모든 버킷에 완벽하게 골고루 분산시킵니다.

B. 적재율 (Load Factor)과 재해싱 (Rehashing)

적재율(Load Factor) 은 해시 테이블이 크기를 늘리기 전까지 얼마나 차 있는지를 나타내는 지표입니다.

$$\text{Load Factor } (\alpha) = \frac{\text{Number of Elements}}{\text{Number of Buckets}}$$

• Java에서 기본 적재율은 0.75입니다.
• 재해싱(Rehashing): 테이블이 75% 찼을 때, 더 이상 데이터를 추가하는 것은 위험합니다(충돌 확률이 급증함). 따라서 시스템은 크기가 두 배인 새로운 배열을 만들고, 기존의 모든 데이터 에 대해 해시값을 처음부터 다시 계산하여 크기가 커진 새 배열에 재배치합니다. 무거운 작업이지만, 테이블의 속도를 유지하기 위해 꼭 필요합니다.

5. 요약 비교 테이블

6. 보안 위협: 해시 충돌 DoS 공격 (Hash-DoS)

충돌은 단순한 성능 문제가 아니라 보안 취약점이기도 합니다.

만약 공격자가 여러분 서버의 해시 함수 알고리즘을 알아냈다면, 의도적으로 완벽히 똑같은 버킷에서 충돌을 일으키는 악성 페이로드(예: 수만 개의 JSON 키)를 만들어 보낼 수 있습니다. 이로 인해 서버는 모든 요청마다 $O(n)$의 작업을 강제로 수행해야 하고, 결국 CPU 과부하로 서버가 다운됩니다. 이를 해시 충돌 서비스 거부 공격 (Hash-DoS) 이라고 부릅니다.

현대의 프로그래밍 언어들은 애플리케이션이 시작될 때마다 해시의 시드(Seed)값을 무작위로 변경하는 방식으로 이 공격을 방어합니다.

충돌이 일어난 부분에서 값을 찾으려고 할 때

시나리오 A: 시스템이 체이닝(Separate Chaining - 연결 리스트)을 사용할 때

이것이 Java의 HashMap이 작동하는 방식입니다.

1. 저장되는 방식:

버킷 59는 연결 리스트의 시작점(head)을 가리키는 포인터를 가지고 있습니다.

[버킷 59] ---> ["apple" | next] ---> ["banana" | next] ---> ["berry" | null]

2. "berry"를 찾는 과정:

• 1단계 (해싱): 시스템이 "berry"를 해싱하여 59를 얻습니다. 곧바로 버킷 59로 점프합니다.
• 2단계 (첫 번째 비교): 첫 번째 노드를 확인합니다. "apple" == "berry"인가요? 아닙니다. next 포인터를 따라 다음으로 넘어갑니다.
• 3단계 (두 번째 비교): 두 번째 노드를 확인합니다. "banana" == "berry"인가요? 아닙니다. next 포인터를 따라 다음으로 넘어갑니다.
• 4단계 (세 번째 비교): 세 번째 노드를 확인합니다. "berry" == "berry"인가요? 맞습니다! 이 값을 반환합니다.

포인터: 이 전략에서는 충돌한 항목들을 서로 엮어주기 위해 메모리에 반드시 next 포인터가 있어야만 합니다. 배열의 버킷은 그저 첫 번째 노드의 포인터만 들고 있을 뿐입니다.

시나리오 B: 시스템이 개방 주소법(Open Addressing - 선형 탐사)을 사용할 때

이것은 평면적인(Flat) 1차원 배열입니다. 연결 리스트도 없고, next 포인터도 없습니다.

1. 저장되는 방식:

삽입할 때, "apple"이 인덱스 59에 들어갑니다. "banana"가 해싱되어 59가 나왔는데 59가 꽉 차 있으니 60으로 이동합니다. "berry"가 해싱되어 59가 나왔는데 59와 60이 모두 꽉 차 있으니 61로 이동합니다.

• [인덱스 59]: "apple"
• [인덱스 60]: "banana"
• [인덱스 61]: "berry"

2. "berry"를 찾는 과정:

• 1단계 (해싱): 시스템이 "berry"를 해싱하여 59를 얻습니다. 곧바로 인덱스 59로 점프합니다.
• 2단계 (첫 번째 비교): 인덱스 59를 확인합니다. "apple" == "berry"인가요? 아닙니다.
• 3단계 (탐사 및 두 번째 비교): 불일치했으므로, 시스템은 자동으로 인덱스 59 + 1 (인덱스 60)을 확인합니다. "banana" == "berry"인가요? 아닙니다.
• 4단계 (탐사 및 세 번째 비교): 인덱스 59 + 2 (인덱스 61)을 확인합니다. "berry" == "berry"인가요? 맞습니다! 이 값을 반환합니다.

아니요, 이 경우에는 포인터가 존재하지 않습니다. 시스템은 말 그대로 단순히 더하기 연산(인덱스에 +1, +2를 하는 수학적 계산)에만 의존하여 배열의 다음 칸(메모리 슬롯)을 찾아갑니다.

핵심 요약 (The Big Takeaway)

서로 다른 여러 문자열이 동일한 해시값 59를 만들어낼 수 있기 때문에, 해시 결과값(59) 하나만으로는 올바른 데이터를 찾았는지 절대로 확신할 수 없습니다. 시스템은 정확히 일치하는 값을 찾을 때까지 매 단계마다 문자열 전체를 일일이 비교(해야만 합니다.

이것이 바로 해시 충돌이 데이터베이스나 애플리케이션을 느려지게 만드는 정확한 이유입니다. 만약 1,000개의 문자열이 모두 59로 해싱되었고 우리가 찾는 값이 맨 마지막에 있다면, 해당 값을 찾기 위해 무려 1,000번의 문자열 비교 연산을 수행해야만 합니다!

해싱 알고리즘 분류

해싱 알고리즘은 완전히 다른 두 가지 제품군으로 나뉩니다: 비암호화(Non-Cryptographic) (극단적인 속도를 위해 설계됨)와 암호화(Cryptographic) (극단적인 보안을 위해 설계됨).

만약 이것들을 섞어 쓴다면—예를 들어 HashMap에 암호화 해시를 쓰거나, 사용자 비밀번호에 비암호화 해시를 쓴다면—시스템이 엄청나게 느려지거나 즉각적으로 해킹당할 것입니다.

업계 표준 해싱 알고리즘들에 대한 분석입니다.

카테고리 1: 비암호화 해시 (스피드광)

이 알고리즘들은 HashMap, 캐싱, 분산 시스템(예: Redis 라우팅), 그리고 빅데이터 처리에 사용됩니다.

목표: 충돌을 피하기 위해 데이터를 완벽하게 골고루 분산시키면서 가능한 한 최대로 빠르게 동작하는 것입니다. 이 알고리즘들은 보안에는 전혀 신경 쓰지 않습니다.

1. MurmurHash (업계 표준)

• 정의: Austin Appleby가 개발한 알고리즘으로, Java의 최신 데이터 구조, Hadoop, ElasticSearch, Cassandra에서 기본적으로 사용하는 해싱 알고리즘입니다.
• 장점: 믿을 수 없을 정도로 빠르며, 훌륭한 "눈사태 효과(Avalanche Effect, 1,000단어짜리 문서에서 글자 하나만 바꿔도 해시 결과가 완전히 달라지는 현상)"를 가지고 있습니다.
• 경고: 공격자가 MurmurHash를 역설계하여 의도적으로 해시 충돌을 일으키기 매우 쉽습니다(Hash-DoS 공격에 취약).

2. xxHash & CityHash

• 정의: Yann Collet이 개발한 xxHash와 구글이 개발한 CityHash입니다.
• 장점: RAM 속도의 물리적 한계치에 가깝게 실행되도록 설계되었습니다. 현대 CPU 아키텍처의 이점을 최대한 활용하여 기가바이트 단위의 텍스트 같은 방대한 데이터를 거의 즉시 해싱합니다. 빅데이터 분석에서 아주 많이 사용됩니다.

카테고리 2: 일반 암호화 해시 (금고)

이 알고리즘들은 디지털 서명, SSL 인증서, 블록체인, 그리고 파일의 무결성을 검증하는 데 사용됩니다.

목표: 해시 결과값으로 원본 데이터를 역산하는 것이 수학적으로 불가능해야 하며, 동일한 결과값을 출력하는 두 개의 입력값을 의도적으로 찾아내는 것 또한 수학적으로 불가능해야 합니다.

1. MD5 및 SHA-1 (몰락한 왕들)

• 정의: 구형 암호화 해시 알고리즘입니다.
• 상태: 파훼됨 및 사용 중단 (BROKEN AND DEPRECATED).
• 몰락 이유: 컴퓨터가 너무 빨라졌습니다. 연구자들은 MD5와 SHA-1 모두에서 의도적으로 충돌을 만들어내는 방법을 성공적으로 찾아냈습니다.
• 현재 용도: 보안 목적으로는 절대 사용해선 안 됩니다. 오늘날에는 오직 "체크섬(Checksum)" 용도로만 쓰입니다. (예: 5GB짜리 게임을 다운로드할 때, 다운로드 중 데이터가 손상되지 않았는지 확인하기 위해 파일의 MD5 해시값을 비교함).

2. SHA-256 (골드 스탠다드)

• 정의: 미국 국가안보국(NSA)이 설계한 SHA-2 제품군의 하나입니다.
• 장점: 256비트의 해시값을 생성합니다. 생성 가능한 결과값의 수는 $2^{256}$개이며, 이는 관측 가능한 우주에 있는 원자의 수와 맞먹습니다.
• 사용처: 비트코인 채굴, SSL/TLS 핸드셰이크, 안전한 고유 식별자 생성 등에 쓰입니다. 현재로서는 뚫을 수 없는(Unbreakable) 알고리즘으로 간주됩니다.

카테고리 3: 비밀번호 해싱 (느림보)

잠깐, 비밀번호에도 최고존엄인 SHA-256을 써야 하는 것 아닐까요? 절대 아닙니다! 이것은 면접에서 아주 자주 나오는 함정입니다. SHA-256은 컴퓨터가 '빠르게' 계산하도록 설계되었습니다. 현대의 그래픽카드(GPU)는 초당 수십억 번 의 SHA-256 해시를 계산해냅니다. 해커가 데이터베이스를 털어가서 "사전 대입 공격(Dictionary Attack, 사전에 있는 모든 단어를 해싱해 보는 것)"을 시도하면 사용자들의 비밀번호가 몇 초 만에 다 뚫립니다.

비밀번호를 보호하려면, 의도적으로 매우 느리고 계산하기 고통스러운 해시 함수가 필요합니다.

1. bcrypt (전통의 강자)

• 정의: Spring Security 및 대다수 웹 프레임워크의 기본 비밀번호 해싱 알고리즘입니다.
• 작동 원리:
  1. 자동으로 솔트(Salt) 를 추가합니다. 해싱 전에 무작위 문자열을 비밀번호에 이어 붙여서, "password123"이라는 똑같은 비밀번호를 가진 두 사용자도 완전히 다른 해시값을 가지게 만듭니다.
  2. 작업 계수(Work Factor/Cost) 를 사용합니다. 계산하는 데 정확히 0.5초가 걸리도록 설정할 수 있습니다. 즉, 해커가 비밀번호를 무작위로 대입해 보려고 해도 시간이라는 물리적 한계에 부딪히게 만듭니다.

2. Argon2 (현대의 왕)

• 정의: 2015년 패스워드 해싱 대회(Password Hashing Competition)의 우승작입니다. 현재 세계에서 가장 안전한 비밀번호 해싱 알고리즘입니다.
• bcrypt를 이긴 이유: 해커들이 수천 개의 GPU를 병렬로 연결하여 bcrypt의 '느림'을 돈과 물량으로 우회하기 시작했습니다. Argon2는 "메모리 하드(Memory-Hard)" 방식을 채택했습니다. 해시를 계산하는 데 엄청난 양의 RAM 메모리를 요구합니다. GPU는 연산력에 비해 장착된 메모리 용량이 매우 적기 때문에, Argon2는 해커들의 값비싼 GPU 채굴/해킹 장비를 완벽한 고철 덩어리로 만들어버립니다.

요약 비교 테이블

SHA-256 - 왜 비트코인은 되고 비번은 안되나

정보의 영구적 손실 (믹서기 비유) 과 인간의 두뇌로는 가늠할 수 없는 우주적 규모입니다.

왜 단순한 컴퓨팅 파워만으로는 SHA-256을 무너뜨릴 수 없는지 설명해 드리겠습니다.

1. SHA-256은 "금고"가 아니라 "믹서기"입니다

사람들은 암호학이라고 하면 튼튼한 자물쇠가 채워진 금고를 떠올립니다. 만약 아주 힘이 센 로봇(GPU)이 있다면, 올바른 번호 조합을 찾을 때까지 다이얼을 수백만 번 빠르게 돌려보면 금고가 열릴 것이라 생각하죠.

하지만 해시 함수는 금고가 아닙니다. 그것은 믹서기(Blender)입니다.

사과와 바나나를 믹서기에 넣고 돌리면 스무디가 됩니다.

• 완성된 스무디만 뚫어져라 쳐다보면서, 수학적인 계산을 통해 원래 사과의 정확한 형태와 크기를 유추해 낼 수 있을까요? 절대 불가능합니다. * 사과의 물리적 구조가 완전히 파괴되었기 때문입니다. 정보가 영구적으로 손실된 것이죠.

SHA-256은 모듈러 덧셈이나 비트 시프트 같은 수학적 연산을 사용하여 데이터를 영구적으로 폐기해버립니다. 해커가 256비트의 해시 결과값을 쳐다본다고 해도, 그 숫자들 안에는 원본 데이터가 아예 존재하지 않습니다. 애초에 방정식을 거꾸로(수학적으로 역산) 푸는 것 자체가 불가능합니다.

2. 해시를 "뚫는" 유일한 방법: 무작위 대입 공격 (찍기)

수학적으로 역산하는 것이 불가능하므로, 해커가 SHA-256 해시를 뚫을 수 있는 유일한 방법은 계속 찍어보는 것뿐입니다.

아무 단어나 골라서 SHA-256 알고리즘(매우 빠름)에 돌려본 뒤, 그 결과값이 자신이 뚫고자 하는 목표 해시값과 일치하는지 확인합니다. 이를 무작위 대입 공격(Brute Force Attack) 이라고 부릅니다.

"GPU가 초당 수십억 번을 찍어볼 수 있다면, 언젠가는 정답을 맞히지 않을까요?"

이 대목에서 인간의 직관은 완전히 무너집니다. 우리는 $2^{256}$이라는 숫자가 얼마나 거대한지 도저히 상상조차 할 수 없기 때문입니다.

3. 상상을 초월하는 $2^{256}$의 규모

SHA-256 해시는 256개의 비트(0과 1)로 이루어져 있습니다. 즉, $2^{256}$개의 가능한 경우의 수가 존재합니다.

$2^{256}$은 얼마나 큰 숫자일까요? 대략 $10^{77}$(1 뒤에 0이 77개 붙은 숫자)과 같습니다. "초당 수십억 번의 해시 연산"이 왜 먼지보다 못한 수준인지 계산해 보겠습니다.

• 지구상에서 가장 강력한 GPU를 샀다고 가정해 봅시다. 이 괴물은 초당 100조 번 ($10^{14}$) 의 해시를 계산할 수 있습니다.
• 이 GPU를 지구상의 모든 인류 (약 80억 명)에게 한 대씩 나눠줍니다.
• 모든 인류가 이 GPU를 1년 365일 24시간 내내 쉬지 않고 돌립니다.
• 이제 전 인류는 힘을 합쳐 매초 $8 \times 10^{23}$번의 해시를 찍어보고 있습니다.

이 지구급 슈퍼컴퓨터가 SHA-256의 모든 가능한 경우의 수를 다 찍어보려면 시간이 얼마나 걸릴까요?

$$\text{시간} = \frac{10^{77} \text{ (전체 경우의 수)}}{8 \times 10^{23} \text{ (초당 찍어보는 횟수)}} = 1.25 \times 10^{53} \text{ 초}$$

$1.25 \times 10^{53}$초가 어느 정도의 시간인지 감을 잡기 위해 비교해 보자면: 이 우주의 전체 나이가 고작 $4 \times 10^{17}$초입니다.

만약 전 인류가 138억 년 전 빅뱅이 일어난 정확히 그 순간부터 오늘날까지 단 1초도 쉬지 않고 해시값을 찍어봤다고 해도, 우리가 확인한 경우의 수는 전체의 0.000000000000000000000000000000000001% 도 되지 않습니다.

이것이 SHA-256이 뚫리지 않는 이유입니다. 이 알고리즘은 수학을 넘어 열역학적, 물리적 한계와 우주의 법칙에 기대어 우리를 보호합니다. 태양만 한 크기의 컴퓨터를 만든다고 해도, $2^{256}$까지 숫자를 세는 데 필요한 에너지가 우주 전체에 존재하지 않습니다.

4. 그렇다면 비트코인 채굴자들은 도대체 뭘 하고 있는 걸까요?

SHA-256을 뚫는 게 불가능하다면, 거대한 공장을 가득 채운 그 수많은 비트코인 채굴용 컴퓨터들은 도대체 뭘 하고 있는 걸까요? 왜 그들은 굳이 SHA-256을 쓸까요?

비트코인 채굴자들은 (누군가의 비밀번호나 지갑 키를 훔치기 위해) 특정한 해시값을 역산하거나 뚫으려고 하는 것이 아닙니다. 그 대신, 그들은 작업 증명(Proof of Work) 이라는 전 세계적인 규모의 복권 추첨 게임을 하고 있는 것입니다.

비트코인 네트워크는 10분마다 새로운 과제를 던져줍니다:

"입력값으로 뭘 쓰든 상관없는데, SHA-256으로 해싱했을 때 앞자리가 0으로 19번 연속 시작하는 결과값을 만들어내는 입력값을 찾아와!"

(예: 0000000000000000000x2b4f...)

해시 결과값은 완벽하게 무작위적이기 때문에, 어떤 입력값을 넣어야 앞자리에 0이 19개 연속으로 나올지 절대 예측할 수 없습니다. 이길 수 있는 유일한 방법은 그저 맹목적으로 계속 찍어보는 것뿐입니다.

1. 채굴자들은 거래 내역이 담긴 블록 데이터 끝에 무작위 숫자(논스, nonce라고 부름)를 하나 이어 붙인 뒤 해싱합니다.
2. 결과값이 0 열아홉 개로 시작하나요? 아닙니다.
3. 그럼 무작위 숫자를 다른 걸로 바꿔서 다시 해싱합니다.
4. 이 과정을 초당 수조 번 반복합니다.

그러다 마침내 누군가가 엄청난 행운으로 잭팟을 터뜨리고(0이 19개인 해시값을 우연히 찾아내고), 이를 전체 네트워크에 전파하여 비트코인 보상을 독식하게 됩니다.

결정적인 차이점 정리:

• 특정 해시 뚫기 (해커의 목표): 우주만 한 크기의 거대한 건초더미에서 정확히 지정된 바늘 하나 를 찾아야 합니다. 절대 불가능합니다.
• 비트코인 채굴: 아주 거대한 건초더미에서 아무 바늘이나 하나 만 찾으면 됩니다. 막대한 전기가 소모될 만큼 극도로 어렵지만, 초당 수조 번씩 찍어본다면 충분히 가능합니다.

비트코인에 비해서 해커들이 데이터베이스 해시를 아주 쉽게 뚫어내는 이유와, 인간의 행동 패턴이 어떻게 SHA-256의 수학적 무적성을 완전히 무력화시키는지 설명해 드리겠습니다.

1. 치명적 결함: 입력 공간 (Input Space) vs 출력 공간 (Output Space)

비트코인에서는 입력값이 무작위이므로 올바른 해시를 찾으려면 전체 "출력 공간"($2^{256}$개의 경우의 수)을 전부 뒤져야 합니다. 앞서 말씀드렸듯 이는 불가능합니다.

하지만 해커가 사용자 비밀번호 데이터베이스를 훔쳤을 때는 $2^{256}$이라는 무한한 출력 공간에는 전혀 관심이 없습니다. 그들은 오직 입력 공간—즉, 사람들이 비밀번호를 만들 때 실제로 사용하는 제한된 문자 조합—에만 관심이 있습니다.

인간은 무작위성을 만들어내는 데 매우 서툽니다. 우리가 아는 단어, 이름, 생년월일, 예측 가능한 패턴을 사용하죠.

• 어떤 사용자가 소문자와 숫자(총 36개의 문자)만 사용하여 8자리 비밀번호를 만들었다고 가정해 봅시다.
• 가능한 전체 조합 수: $36^8 \approx 2.8 \times 10^{12}$ (약 2조 8천억 개).

현대의 단일 GPU는 초당 수십억 번의 SHA-256 해시를 계산할 수 있습니다. 이 GPU는 소문자와 숫자로만 된 8자리 비밀번호의 모든 경우의 수를 단 20분 안에 다 찍어볼 수 있습니다. 해커는 SHA-256의 $10^{77}$가지 경우의 수를 다 찍어볼 필요가 없습니다. 귀찮음이 많은 인간이 실제로 입력했을 법한 2조 8천억 개의 경우의 수만 찍어보면 되는 것입니다.

2. 해커의 플레이북: 유출된 데이터베이스를 뚫는 방법

해커가 여러분의 데이터베이스를 다운로드하고 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8 같은 해시값을 발견하면, 주로 두 가지 기술을 사용합니다:

A. 사전 대입 공격 (Dictionary Attack)

해커들은 사람들이 가장 많이 쓰는 수십억 개의 비밀번호(password123, qwerty, admin, Iloveyou 등)와 영어 사전의 모든 단어가 통째로 담긴 거대한 텍스트 파일을 가지고 있습니다.

그들은 단순히 이 텍스트 파일을 SHA-256 믹서기에 돌려봅니다. SHA-256은 너무나도 빠르기 때문에, GPU는 단 몇 초 만에 100억 개의 단어로 된 사전을 모두 해싱할 수 있습니다. 그 결과 나온 해시값이 데이터베이스에 적힌 해시값과 일치하면, 곧바로 비밀번호를 알아낸 것입니다.

B. 레인보우 테이블 (Rainbow Tables)

공격할 때마다 매번 해시를 계산할 필요가 있을까요? 미리 다 계산해 두면 되는데요!

해커들은 1자리에서 10자리 사이의 모든 가능한 비밀번호 조합에 대해 SHA-256 해시값을 미리 계산한 뒤, 이를 레인보우 테이블이라는 거대한 데이터베이스에 저장해 둡니다.

여러분의 데이터베이스를 훔쳤을 때 그들은 수학 계산을 전혀 하지 않습니다. 그냥 단순한 DB 검색만 할 뿐이죠: "이 해시값이 내 레인보우 테이블에 있나? 어, 있네? 그럼 이 비밀번호는 'apple123'이군."

3. SHA-256이 데이터베이스에 "최악"인 이유

이것이 아주 중요한 핵심으로 이어집니다: 비밀번호 저장에 있어서는, SHA-256의 '빠른 연산 속도'가 오히려 엄청난 보안 취약점이 됩니다.

SHA-256은 극도로 효율적으로 작동하도록 설계되었기 때문에, 해커의 GPU가 초당 수십억 번의 사전 대입 공격을 할 수 있게 허락해 줍니다. 사용자 비밀번호를 해싱하는 데 SHA-256을 쓴다는 것은, 해커에게 여러분의 비밀번호 방어막을 시속 300km로 뚫고 지나갈 스포츠카를 쥐어주는 것과 같습니다.

4. 우리가 방어하는 방법 (데이터베이스의 갑옷)

제한된 문자 조합의 약점을 파고들어 데이터베이스를 크랙하려는 해커를 막으려면, 게임의 규칙 자체를 바꿔야 합니다. 그래서 우리는 bcrypt나 Argon2 같은 비밀번호 전용 알고리즘을 사용하여 두 가지 강력한 방어막을 도입합니다:

방어 1: "솔트 (Salt)" (레인보우 테이블 무력화)

비밀번호를 해싱하기 전에, 데이터베이스는 완전히 무작위로 생성된 긴 문자열(솔트)을 만들어 사용자의 비밀번호에 이어 붙입니다.

• 사용자 입력값: apple123
• 솔트(무작위 생성): XyZ98pLq
• 실제로 해싱되는 텍스트: apple123XyZ98pLq

이 솔트값은 모든 사용자마다 완전히 다르게(고유하게) 생성됩니다. 즉, 해커가 미리 계산해 둔 레인보우 테이블을 아예 쓸 수 없게 됩니다. 레인보우 테이블은 이 무작위 솔트값이 무엇인지 모르기 때문입니다. 결국 해커는 모든 개별 사용자에 대해 처음부터 다시 해시를 계산해야만 합니다.

방어 2: "작업 계수 (Cost Factor)" (무작위 대입 및 GPU 무력화)

앞서 논의했듯, bcrypt나 Argon2 같은 알고리즘은 의도적으로 엄청나게 느리게 작동하도록 엔지니어링되었습니다. 우리는 알고리즘이 해시 하나를 계산하는 데 정확히 0.5초가 걸리도록 설정할 수 있습니다.

• 해커가 SHA-256 해시를 상대로 8자리 조합 2조 8천억 개를 다 찍어보려면 GPU로 20분이면 됩니다.
• 하지만 해커가 bcrypt 해시를 상대로 동일한 2조 8천억 개를 다 찍어보려고 하면 (계산당 0.5초 소요), 무려 4만 4천 년이 걸립니다.

일반 사용자가 로그인할 때 0.5초 정도 로딩이 걸리는 것은 전혀 체감하지 못하지만, 이 0.5초의 지연은 초당 수십억 번을 찍어보려는 해커의 GPU 파워를 완벽하게 고철 덩어리로 만들어버립니다.

references